#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<string>
#include<vector>
#include<unordered_map>
using namespace std;
class Solution1
{
public:
    int findMaxLength(vector<int>& nums)
    {
        for (auto& x : nums)
        {
            if (x == 0)
                x = -1;
        }
        int len = 0, sum = 0;
        unordered_map<int, int> hash;
        hash[0] = 0;
        for (int i = 0;i < nums.size();i++)
        {
            sum += nums[i];
            if (sum==0 ||hash[sum]>0)
            {
                int tmp = i +1- hash[sum] ;
                len = tmp > len ? tmp : len;
            }
            if (!hash[sum]&&sum!=0)
                hash[sum] = i + 1;
        }
        return len;

    };
};
class Solution5
{
public:
    int findMaxLength(vector<int>& nums)
    {
        for (auto& x : nums)
        {
            if (x == 0)
                x = -1;
        }
        int len = 0, sum = 0;
        unordered_map<int, int> hash;
        hash[0] = -1;
        for (int i = 0;i < nums.size();i++)
        {
            sum += nums[i];
            if (hash.count(sum))
            {
                int tmp = i - hash[sum];
                len = tmp > len ? tmp : len;
            }
            if (!hash.count(sum))
                hash[sum] = i;
        }
        return len;

    };
};
class Solution1234 {
public:
    int hammingDistance(int x, int y)
    {
        int cnt = 0, test = 1;
        for (int i = 0;i < 32;i++)
        {
            int x1 = x & test;
            int y1 = y & test;
            if (x1 != y1) 
                cnt++;
            test <<= 1;
        }
        return cnt;
    }
};
class Solution
{
public:
    int findKthLargest(vector<int>&nums, int k)
    {
        srand(time(NULL));
        return mysort(nums,k,0,nums.size() - 1);
    }
    int mysort(vector<int>&nums,int k,int left,int right)
    {
        int key = getRandom_index(nums,left,right);
        int l = left - 1,r = right + 1,cur = left;
        while (cur < r)
        {
            if (nums[cur] < key) swap(nums[--l],nums[cur++]);
            else if (nums[cur] > key) swap(nums[cur],nums[--r]);
            else cur++;
        }
        if (right - r + 1 >= k) return mysort(nums,k,r,right);
        else if (right - (l + 1) + 1 >= k) return nums[l + 1];
        else return mysort(nums,k - (right - (l + 1) + 1),left,l);
    }
    int getRandom_index(vector<int>&nums,int left,int right)
    {
        int len = rand() % (right - left + 1);
        return nums[left + len];
    }
};
int main()
{
	vector<int> v = {3,2,1,5,6,4};
    /*Solution().findMaxLength(v);*/
    /*Solution().hammingDistance(1,4);*/
    Solution().findKthLargest(v, 2);
	return 0;
}